﻿using System.Collections.Generic;

//数据结构：最小堆
namespace Game.DataStruct
{

    /// <summary>
    /// 最小堆，出堆顺序为：永远取堆中最小的内个
    /// </summary>
    class MinHeap<T>
    {
        /// <summary>
        /// 堆物体
        /// </summary>
        private class HeapObj<T1>//取名T1，避免类型名与外部的T一样
        {
            /// <summary>
            /// 数据段
            /// </summary>
            public T1 obj;

            /// <summary>
            /// 堆中权重
            /// </summary>
            public int weight;

            public HeapObj(T1 obj, int weight)
            {
                this.obj = obj;
                this.weight = weight;
            }
        }

        //--以动态数组即可模拟最小堆（因为其组织结构就是满二叉树）
        private List<HeapObj<T>> m_heapObjs = new List<HeapObj<T>>();

        //---------------------------------------------------------------------------
        //				Public area
        //---------------------------------------------------------------------------
        #region Public area

        /// <summary>
        /// 往堆中添加物体
        /// </summary>
        /// <param name="obj">obj</param>
        /// <param name="weight">权重</param>
        public void AddObj(T obj, int weight)
        {
            HeapObj<T> heapObj = new HeapObj<T>(obj, weight);

            //在堆最后添加新来的，再往上调整
            m_heapObjs.Add(heapObj);

            ShiftUp();
        }

        /// <summary>
        /// 获得堆中第一个最小权重的元素
        /// </summary>
        /// <returns></returns>
        public T PopObj()
        {
            HeapObj<T> heapObj = PopTopHeapObj();
            if (heapObj == null)
            {
                return default(T);
            }
            else
            {
                return heapObj.obj;
            }
        }

        #endregion

        //---------------------------------------------------------------------------
        //				Private area
        //---------------------------------------------------------------------------
        #region Private area

        /// <summary>
        /// 获得堆中第一个最小权重的HeapObj
        /// </summary>
        /// <returns></returns>
        private HeapObj<T> PopTopHeapObj()
        {
            if (m_heapObjs.Count <= 0)
            {
                return null;
            }

            HeapObj<T> result = m_heapObjs[0];

            //将堆中最后一个元素放到顶部，再往下调整
            int tailIndex = m_heapObjs.Count - 1;
            HeapObj<T> tailObj = m_heapObjs[tailIndex];
            m_heapObjs.RemoveAt(tailIndex);
            //非空时才将最后一个调整到堆顶
            if (m_heapObjs.Count > 0)
            {
                m_heapObjs[0] = tailObj;
            }

            ShiftDown();

            return result;
        }


        /// <summary>
        /// 从堆最后一个元素，从下往上调整，直到符合最小堆规则
        /// </summary>
        private void ShiftUp()
        {
            if (m_heapObjs.Count <= 1)
            {
                return;
            }

            int currIndex = m_heapObjs.Count - 1;
            int parentIndex = -1;
            HeapObj<T> currNode = null, parentNode = null;

            while (currIndex > 0)
            {
                currNode = m_heapObjs[currIndex];

                //--获得父节点，并与之比较,如果当前节点更适合当父节点，则交换之：
                parentIndex = GetParentIndex(currIndex);
                parentNode = m_heapObjs[parentIndex];
                if (currNode.weight < parentNode.weight)
                {
                    Swap(currIndex, parentIndex);
                }
                else
                {
                    //--当前节点不需要往上调整，则跳出循环
                    break;
                }

                currIndex = parentIndex;
            }
        }

        /// <summary>
        /// 从堆顶往下调整直到符合最小堆原则
        /// </summary>
        private void ShiftDown()
        {
            int count = m_heapObjs.Count;

            if (count <= 1)
            {
                return;
            }


            int currIndex = 0, minIndex = -1, rightChildIndex;          //当前下标，最小的子节点下标，右子节点下标
            HeapObj<T> currNode = null, childNodeMin = null;                          //当前节点，最小子节点

            int travelEndIndex = GetParentIndex((count - 1));            //只需要调整到倒数第二层，(最大下标/2)将保证遍历时至少有一个左子节点

            while (currIndex <= travelEndIndex)
            {
                currNode = m_heapObjs[currIndex];

                minIndex = currIndex * 2 + 1;                                       //假设左子节点为最小
                rightChildIndex = minIndex + 1;                               //右子节点

                //存在右子节点的情况下,左右比较,如果右边更小，则最小子节点设置为右边的节点
                if (rightChildIndex < count && (m_heapObjs[rightChildIndex].weight < m_heapObjs[minIndex].weight))
                {
                    minIndex = rightChildIndex;
                }

                childNodeMin = m_heapObjs[minIndex]; ;

                //--子节点小，则交换之，并往子节点继续调整：
                if (childNodeMin.weight < currNode.weight)
                {
                    Swap(minIndex, currIndex);
                    currIndex = minIndex;
                }
                else
                {
                    break;
                }
            }
        }

        /// <summary>
        /// 交换两个位置的元素
        /// </summary>
        private void Swap(int src, int dst)
        {
            HeapObj<T> srcObj = m_heapObjs[src];

            m_heapObjs[src] = m_heapObjs[dst];
            m_heapObjs[dst] = srcObj;
        }

        /// <summary>
        /// 获得该节点的父节点的下标
        /// </summary>
        private int GetParentIndex(int index)
        {
            return (index - 1) / 2;
        }

        //public string TEST_ToString()
        //{
        //    StringBuilder sb = new StringBuilder();
        //    for (int i = 0; i < m_heapObjs.Count; i++)
        //    {
        //        HeapObj<T> obj = m_heapObjs[i];
        //        sb.Append(obj.weight + " ");
        //    }
        //    return sb.ToString();
        //}

        #endregion

    }


}